/**
 * 938. 二叉搜索树的范围和
 * https://leetcode-cn.com/problems/range-sum-of-bst/
 */
public class Solutions_938 {
    public static void main(String[] args) {
        String str = "[10 5 15 3 7 # 18]";
        int low = 7, high = 15;  // output: 32

//        String str = "[10 5 15 3 7 13 18 1 # 6]";
//        int low = 6, high = 10;  // output: 23

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        int result = rangeSumBST(root, low, high);
        System.out.println(result);
    }

    private static int res = 0;

    /**
     * 递归方式实现二叉搜索树的中序遍历
     * 递归解法比栈模拟的解法要快
     */
    public static int rangeSumBST(TreeNode root, int low, int high) {
        dfs(root, low, high);
        return res;
    }

    public static void dfs(TreeNode root, int left, int right) {
        if (root == null) {
            return;
        }
        dfs(root.left, left, right);
        if (root.val >= left && root.val <= right) {
            // 节点值位于 [left, right] 之间
            res += root.val;
        }
        if (root.val > right) {
            // 不用再往后遍历
            return;
        }
        dfs(root.right, left, right);
    }
}
